#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {


	int m = triangle.size();
	vector<vector<int>>dp(m);
	if (m == 0) return 0;
	if (m == 1) return triangle[0][0];
	dp[0] = vector<int>(1);
	dp[0][0] = triangle[0][0];
	for (int i = 1; i < m; i++) {
		dp[i] = vector<int>(i + 1);
		dp[i][0] = dp[i - 1][0] + triangle[i][0];
		dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
	}
	for (int i = 2; i < m; i++) {
		for (int j = 1; j < i ; j++) {
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
		}
	}
	int min = dp[m - 1][0];

	for (int j = 1; j < m; j++) {
		if (min > dp[m - 1][j]) min = dp[m - 1][j];
	}
	return min;


}

